package com.leetcode.algo;

import java.util.HashSet;
import java.util.Set;

/**
 * 
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串""。
 *
 * 示例 1：
 *
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 示例 2：
 *
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Algo14 {

    public String longestCommonPrefix(String[] strs) {

        StringBuilder longPrefix = new StringBuilder("");
        int index = 0;

        while(true) {
            Set<Character> checkSet = new HashSet<>();
            for (String str : strs) {
                if (index < str.length()){
                    checkSet.add(str.charAt(index));
                }else {
                    return longPrefix.toString();
                }
            }
            if (checkSet.size() != 1){
                break;
            }else {
                checkSet.forEach(c -> {
                    longPrefix.append(c);
                });
            }
            index++;
        }

        return longPrefix.toString();

    }

    /**
        没啥区别我靠
        12%
     */
    public String longestCommonPrefix2(String[] strs) {

        int index = 0;

        StringBuilder longestPrefixStrb = new StringBuilder("");
        boolean flag = true;
        while(flag) {

            Set<Character> checkSet = new HashSet<>();
            for (int i = 0; i < strs.length; i++) {
                if (index > strs[i].length() - 1) {
                    checkSet.clear();
                    flag = false;
                    break;
                }else {
                    checkSet.add(strs[i].charAt(index));
                }
            }

            if (checkSet.size() == 1) {
                checkSet.forEach(character -> {
                    longestPrefixStrb.append(character);
                });
            }else {
                flag = false;
            }

            index++;
        }

        return longestPrefixStrb.toString();
    }

    /**
     * 想复杂了
     * @param strs
     * @return
     */

    public String longestCommonPrefix3(String[] strs) {

        if (strs == null || strs.length == 0) {
            return "";
        }
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    public static void main(String[] args) {

    }

}
